\chapter{顺序表与单链表}
\section{实验目的}

\begin{itemize}
  \item 通过本次实验进一步加深对线性表的理解,在此基础上实现线性表的顺序表示(顺 序表)及链式表示(单链表)。
  \item 掌握线性表的基本操作(包括:创建、插入、删除、查 找等基本操作)。
  \item 在掌握基本操作的基础上, 对实验给出的扩展实验题目进行分析、建模。使用顺序表或单链表及简单的算法解决问题。
\end{itemize}

\section{基础实验题目}
在本次实验当中，你需要实现顺序形式(顺序表)以及单链形式(单链表)表示线性表，其中顺序表及单链表的结构定义及操作接口定义分别见\ref{sec:seqlist}和\ref{sec:lnlist}。

需要注意的是，在本次实验当中，你需要完成\ref{sec:seqlist}和\ref{sec:lnlist}的内容，在完成上述内容后，请使用你实现的顺序表及单链表完成\ref{sec:listtest}所给出的题目，用于测试你的程序是否正确。

\subsection{顺序形式表示线性表}
\label{sec:seqlist}
使用顺序形式表示线性表，称之为顺序表。以下给出顺序表的数据结构定义以及操作接口声明(C语言描述)\footnote{以上定义了顺序表的基本结构,你也可根据自己的理解或问题的实际需求定义顺序表的数据结构,此外实现的语言不限,可以是C/C++、Java 等。}:

\captionof{listing}{顺序表数据结构定义及操作接口声明}
\label{lstseqadt}
\begin{minted}[linenos, frame=single]{c}
typedef int ELEMTYPE;
typedef int POSITION;
typedef int SIZE_T;

struct SQList {
  ELEMTYPE *elements;
  SIZE_T length;
  SIZE_T maxNum;
};

typedef struct SQList *SeqList;

/*
 * description:  创建指定长度的顺序表
 * return value: 成功则返回线性表的指针,否则返回NULL
 * author:       xgqin@guet.edu.cn
 * date:         2013-05-03
 */
SeqList createSeqList(SIZE_T length);

/*
 * description:  删除顺序表elements域及SeqList
 * return value: void
 * author:       xgqin@guet.edu.cn
 * date:         2013-05-03
 */
void destroySeqList(SeqList list);

void printSeqList(SeqList list);
SIZE_T lengthSeqList(SeqList list);

int getVertexSeqList(SeqList list, POSITION p, ELEMTYPE *x);
POSITION locateVertexSeqList(SeqList list, ELEMTYPE x);

int insertPreSeqList(SeqList list, POSITION p, ELEMTYPE x);
int insertPostSeqList(SeqList list, POSITION p, ELEMTYPE x);
int appendElemSeqList(SeqList list, ELEMTYPE x);

int deleteElemSeqList(SeqList list, ELEMTYPE x);
int deleteVertexSeqList(SeqList list, POSITION p);
\end{minted}

在代码\ref{lstseqadt}中，我们为\emph{SQList}结构体定义了3个成员：
\begin{itemize}
  \item \emph{elements}用于指向分配给\emph{SQList}存储数据元素的存储空间首地址；
  \item \emph{length}用于记录\emph{SQList}所表示的顺序表数据类型中当前包含的数据元素个数；
  \item \emph{maxNum}用于表示创建的\emph{SQList}顺序表所能存储的数据元素个数；
\end{itemize}

为数据结构多设计一个成员用于存储\emph{长度}等信息通常而言是十分有帮助的。
在以后的实验当中，我们也经常采用这类做法。

%\subsubsection*{顺序表基本操作的定义(C语言描述):}

%在给出了顺序表的数据结构定义后，我们给出顺序表的基本操作结构定义，如代码\ref{lstseqadt}所示。

在基本操作接口定义中，我们在每个操作申明前使用C语言\emph{块注释}的形式给出了对操作的描述信息，
包括\emph{description}，\emph{return value}，\emph{author}，\emph{date}等信息，
这类信息对于程序维护而言是极其重要的，建议大家在日常编码中学习借鉴一下。

以下给出代码\ref{lstseqadt}所列出的接口的功能性描述信息：
\begin{description}
  \item[\emph{createSeqList}]    创建指定长度的顺序表，如果成功则返回顺序表指针，否则返回\emph{NULL}；
  \item[\emph{destroySeqList}]   删除顺序表,包括删除顺序表的\emph{elements}域及\emph{SeqList}；
  \item[\emph{printSeqList}]     输出顺序表所有的数据元素,这类函数通常用于测试；
  \item[\emph{lengthSeqList}]    获取顺序表的长度,实现时需考虑参数\emph{list}是否为空；
  \item[\emph{getVertexSeqList}]    获取由\emph{POSITION p}所指定的数据元素的值,需要考虑$p$是否在顺序表的下标范围之内(0$\sim$length-1)，如果p满足要求则将数据元素赋给\emph{ELEMTYPE *x}，否则\emph{ELEMTYPE *x}应为\emph{NULL}，且设置相应的函数返回值；
  \item[\emph{locateVertexSeqList}] 查找某个数据值$x$是否在顺序表\emph{list}中,如果存在则返回第一次出现该值的数据结点的下标,若不存在则返回 一个特殊值
  \item[\emph{insertPreSeqList}]    在\emph{POSITION p}指向的数据元素前插入一个新的元素x，需要考虑当前的\emph{list}顺序表是否还可继续插入新元素,亦即\emph{list}的\emph{length}域是否小于\emph{maxNum}域；
  \item[\emph{insertPostSeqList}]   在\emph{POSITION p}指向的数据元素后插入一个新的元素 x,需要考虑当前的\emph{list}顺序表是否还可继续插入新元素,亦即\emph{list}的\emph{length}域是否小于\emph{maxNum}域；
  \item[\emph{appendElemSeqList}]   在顺序表的尾部,添加一个新的 数据元素,其数据域为\emph{x}；
  \item[\emph{deleteElemSeqList}]   在顺序表\emph{list}中,删除第一个值 为\emph{x}数据元素,如果存在的话；
  \item[\emph{deleteVertexSeqList}] 在顺序表\emph{list}中,删除\emph{POSITION p}所指向的数据元素,如果\emph{p}满足顺序表的下标范围要求时(0$\sim$length-1)；
\end{description}

在本例中，所有操作接口均可通过其函数名直观的理解每个操作的功能。本例中，我们对每个操作接口均给出了较详细的描述。\emph{在本书之后的其他操作接口均不在给出功能性的描述信息，你应该能通过操作接口命名及所学理论知识判断该操作接口应完成的功能}。

注意到上述C语言形式描述的任意一个操作接口定义中形参均包含\emph{SeqList list}，且每个操作接口均是形如\emph{operation}\textbf{SeqList}的形式，其中\emph{operation}是操作接口实际命名(通常采用动宾短语形式)，而\textbf{SeqList}则表示顺序表的后缀。

\subsection{链式形式表示线性表}
\label{sec:lnlist}

在此给出单链表的数据结构定义(C语言描述):

\captionof{listing}{单链表数据结构定义及操作接口声明}
\begin{minted}[linenos, frame=single]{c}
typedef int ELEMTYPE;

struct LNode;
struct LNode {
  ELEMTYPE info;
  struct LNode *link;
};

typedef struct LNode *PNode;
typedef struct LNode *POSITION;
struct lnList {
  PNode head;
  PNode rear;
  int length;
};
typedef struct lnList *LnList;

LnList createLnList(void);
void destroyLnList(LnList *list);

void printLnList(LnList list);
int lengthLnList(LnList list);

int insertPostLnList(LnList list, POSITION p, ELEMTYPE x);
int insertPreLnList(LnList list, POSITION p, ELEMTYPE x);

POSITION locateVertexLnList(LnList list, ELEMTYPE x);

int deleteELemLnList(LnList list, ELEMTYPE x);
int deleteVertexLnList(LnList list, POSITION p);
int appendElemLnList(LnList list, ELEMTYPE x);

\end{minted}

图\ref{fig:linklist}给出了构造好的单链表示意图，从图中可知LnList指针的head域指向链表的头结点(图中灰色节点)，tail域始终指向尾结点。

\begin{figure}[thp]
  \label{fig:linklist}
  \centering
  \caption{单链表实例示意图}
  \includegraphics[width=\textwidth]{images/ch01/linklist-1.eps}
\end{figure}

\subsection{测试题目}
\label{sec:listtest}

请使用你在\ref{sec:seqlist}和\ref{sec:lnlist}中所实现的顺序表及单链表来完成本节内容。
并编写相应的测试程序对你所创建的顺序表及单链表进行测试,以下给出测试样例要求:

\subsubsection*{问题描述}

在本题中，你需要编写程序用于解析题目所给出的各类线性表操作的命令，并测试你所实现的顺序表及单链表所定义的
操作接口是否能正确的工作。

\subsubsection*{输入数据格式}

输入包含1个测试用例，第一行只有一个整型数$N(0 < N < 100)$,表明接下来有$N$行命令, 命令可以为如下格式：

\begin{small}
\begin{description}
  \item[CREATE m] 创建一个长度为$m$表，其中$m$为整型数，且$0 < m < 100$。
  \item[DESTROY]  销毁表；表销毁后不可再使用。
  \item[PRINT]    在一行中打印出表中所有元素，每个元素之间用一个空格作为间隔，注意最后一个元素后无空格。
  \item[LENGTH]   输出表的长度。
  \item[ELEMENT p] 获取下标为$p$的节点，并将其元素值作为单独一行输出。题目确保$p$是合法有效的范围($0 <= p <= \textbf{size()}-1$)。
  \item[FIND x]   查找表中是否存在元素值为$x$的结点，如果存在的话则输出该节点的下标，如果不存在则输出$-1$。  
  \item[BEFORE p x] 在下标为$p$的结点\textbf{前}插入一个新的结点，其值为$x$；我们确保$p$是合法有效的范围($0 <= p <= \textbf{size()}-1$)。
  \item[AFTER p x] 在下标为$p$的结点\textbf{后}插入一个新的结点，其值为$x$；我们确保$p$是合法有效的范围($0 <= p <= \textbf{size()}-1$)。
  \item[DELETE x] 删除表中元素值为$x$的第一个结点。
  \item[REMOVE p] 删除表中下标为$p$的结点；我们确保$p$是合法有效的范围($0 <= p <= \textbf{size()}-1$)。
  \item[APPEND x] 在表的尾部添加一个新结点，其元素值为$x$。
\end{description}
\end{small}

\subsubsection*{输出格式}

对于输入中的每一个命令，按照其命令的含义及要求输出(注意：请不要多输出也不要少输出)。

\subsubsection*{输入样例}

\begin{lstlisting}[frame=none, numbers=none]
  11
  CREATE 5
  APPEND 1
  AFTER 0 2
  AFTER 0 3
  AFTER 0 4
  AFTER 0 5
  PRINT
  REMOVE 3
  REMOVE 3
  PRINT
  DESTROY
\end{lstlisting}

\subsubsection*{输出样例}
\begin{lstlisting}[frame=none, numbers=none]
  1 5 4 3 2
  1 5 4
\end{lstlisting}

\subsubsection*{Hint}
在单链表操作接口定义中，结点位置采用\textbf{POSITION}类型表示，
而本题目中，插入、删除等操作时，结点位置则采用\textbf{int}型表示。
为了能兼容本题目命令格式，可以考虑实现一个操作接口，该接口将\textbf{int}型表示的结点编号
转换为\textbf{POSITION}型，以下给出一个接口实现的定义：
\captionof{listing}{getPositionByIndex操作接口定义}
\label{Index2Pos}
\begin{minted}[linenos, frame=single]{c}
POSITION getPositionByIndexLnList(LnList list, SIZE_T index)
{
  SIZE_T i, length;
  POSITION p;

  if (list == NULL)
    return NULL;
  
  length = lengthLnList(list);
  if (index > length)
    return NULL;
  
  for (i = 0, p = list->head->link; i < index; ++i)
  {
    p = p->link;
  }
  
  return p;
}
\end{minted}
\section{扩展实验题目}

\subsection{烦人的海报墙}
\subsubsection*{问题描述}
在学校的学生公寓楼内，每栋楼大厅内的宣传栏上每天都有大量的海报。
为了使用一种特殊的方法清理宣传栏而不留下难看的痕迹，事先需要知道宣传栏上张贴海报的位置信息。
为了简化问题我们规定:
\begin{enumerate}
  \item 宣传栏用一个区间[0, 1000000]来表示。
  \item 假设海报的高度均与宣传栏的高度相同，各海报用两个整数left和right (right>left)来表示,表示海报占据区间[left, right]；我们确保$0 \leq \textbf{left, right} \leq 1000000$
  \item 两张海报是可以部分或者全部重叠的。
  \item 所有海报都不会超过宣传栏的大小。根据给定的每张海报所占据的区间，请你计算出在宣传栏上所有贴有海报的连续区间。
\end{enumerate}

\emph{编程任务:}

根据给定的每张海报所占据的区间,请你计算出在宣传栏上所有贴有海报的连续区间。

\subsubsection*{输入格式}
输入包含多个测试用例，每个测试用例第一行为整型数$n$ ($0 < n < 1000$)，表示接下来有$n$行；
接下来的$n$行中，每行包含2个整型数\emph{left}和\emph{right}，
它们之间有一个空格。最后一个测试用例以0作为开头，该测试用例不需要处理。

\subsubsection*{输出格式}
对于每个测试用例输出可表示的最大连续区间；每个区间单独作为一行输出，
表示该区间的\emph{left}和\emph{right}之间有一个空格作为间隔。
如果对于一个测试用力输入而言，如果有多个连续区间，
则按照区间的\emph{left}的大小，从小到大依次输出区间。

\subsubsection*{输入样例}
\begin{lstlisting}[frame=none, numbers=none]
3
1 5
2 8
9 20
0
\end{lstlisting}

\subsubsection*{输出样例}
\begin{lstlisting}[frame=none, numbers=none]
1 8
9 20
\end{lstlisting}
